<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <div class="parent">
      <div class="child-1">
        <div class="child-1-1">
          <div class="child-1-1-1">
            a
          </div>
        </div>
        <div class="child-1-2">
          <div class="child-1-2-1">b</div>
        </div>
        <div class="child-1-3">
          c
        </div>
      </div>
      <div class="child-2">
        <div class="child-2-1">d</div>
        <div class="child-2-2">e</div>
      </div>
      <div class="child-3">
        <div class="child-3-1">f</div>
      </div>
    </div>
    <script>
      //参考文章：https://github.com/Advanced-Frontend/Daily-Interview-Question/issues/9
      // 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，
      // 则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；
      // 然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，
      // 则以w为新的出发点继续进行深度优先遍历，
      // 直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。
      // 若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，
      // 直至图中所有顶点均已被访问为止。
      /*深度优先遍历三种方式*/
      let deepTraversal1 = (node, nodeList = []) => {
        if (node !== null) {
          nodeList.push(node);
          let children = node.children;
          for (let i = 0; i < children.length; i++) {
            deepTraversal1(children[i], nodeList);
          }
        }
        return nodeList;
      };
      let deepTraversal2 = (node) => {
        let nodes = [];
        if (node !== null) {
          nodes.push(node);
          let children = node.children;
          for (let i = 0; i < children.length; i++) {
            nodes = nodes.concat(deepTraversal2(children[i]));
          }
        }
        return nodes;
      };
      // 非递归
      let deepTraversal3 = (node) => {
        let stack = [];
        let nodes = [];
        if (node) {
          // 推入当前处理的node
          stack.push(node);
          while (stack.length) {
            let item = stack.pop();
            let children = item.children;
            nodes.push(item);
            // node = [] stack = [parent]
            // node = [parent] stack = [child3,child2,child1]
            // node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
            // node = [parent, child1-1] stack = [child3,child2,child1-2]
            for (let i = children.length - 1; i >= 0; i--) {
              stack.push(children[i]);
            }
          }
        }
        return nodes;
      };
      //  广度优先搜索是按层来处理顶点，距离开始点最近的那些顶点首先被访问，
      // 而最远的那些顶点则最后被访问，这个和树的层序变量很像，BFS的代码使用了一个队列
      let widthTraversal2 = (node) => {
        let nodes = [];
        let stack = [];
        if (node) {
          stack.push(node);
          while (stack.length) {
            let item = stack.shift();
            let children = item.children;
            nodes.push(item);
            // 队列，先进先出
            // nodes = [] stack = [parent]
            // nodes = [parent] stack = [child1,child2,child3]
            // nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
            // nodes = [parent,child1,child2]
            for (let i = 0; i < children.length; i++) {
              stack.push(children[i]);
            }
          }
        }
        return nodes;
      };
    </script>
  </body>
</html>
